1. Field of the Invention
The present invention relates to the error correction field and the technology to perform parallel processing in signal processing relating to communication lines.
The invention also relates to the technology to produce syndromes, GCD (greatest common divisor), and error correction in decoding of BCH (Bose-Chaudhuri-Hocqueghem) code.
The invention further relates to signal processing technology in which there are provided three kinds of cells to execute the respective steps of the production of syndromes, production of error position polynomials and error evaluation polynomials, and evaluation and correction of errors in position and size in decoding of BCH code. Only a predetermined number of cells among required cells are one-dimensionally arranged in accordance with the capability of the code.
2. Related Background Art
In recent years, in order to improve the reliability of various kinds of digital systems including the memory system, error detection-correction code (hereinafter, simply referred to as error correction code) has frequently been applied.
The error correction code includes various kinds of codes according to the system in which the error is detected and corrected. One class of linear codes called the cyclic code is the most typical one. This linear code contains BCH code suitable for the random error correction, Fire code suitable for the burst error correction, RS (Reed Solomon) code which is a type of BCH code and fitted for the byte error correction, and the like. Among them, the RS code has the feature such that the lowest redundancy can be obtained in the linear code having the same code length and correcting capability. Therefore, the RS code is widely used for satellite communications, magnetic disks, compact discs (hereinafter, abbreviated as a CD), and the like.
There are various kinds of methods of decoding the RS code and it is possible to provide a decoder for a code having a small correcting capability. However, to obtain high reliability, the correcting capability and code length needs to be enlarged. In this case, there are problems that the scale and control of the apparatus become fairly complicated and it requires a long calculating time for the decoding process. There are the Peterson system and Berlekamp-Massey system as the decoding system of the BCH code of the error correction code. Hitherto, the Peterson system has been used to decode the BCH code the necessary hardware when the correcting capability is low is relatively simple. On the contrary, in the case of providing hardware of the Berlekamp-Massey system, its constitution and control become extremely complicated, so that its realization is difficult.
Therefore, in the current CD system, a kind of double encoder called a CIRC is used and the decoding is performed on the basis of the Peterson system. However, in the case of using this method in the system which requires higher processing speed and high reliability, a problem occurs. In addition, there is the case where high processing speed and high reliability are needed in the communication line as well. It is often very difficult to provide the hardware for this type of communication line. Therefore, this line can be realized by using a simple system to constitute the hardware or limiting the correcting capability. For example in the encoding of the communication path, it is presently possible that up to a double correction of the RS (Reed Solomon) code can be realized.
Further, there is the problem that it takes a fairly long time to realize the foregoing process by the software, so that this method cannot be applied.
Due to the various kinds of problems as mentioned above, there is the problem that it is difficult to realize the RS decoding method having the high correcting capability and long code length and high reliability.